一、取模运算

1.定义：取模运算：运算结果得到的是一个数除以另一个数的余数。

2.举例：给定两个正整数：被除数 a 和除数 n，a modulo n (缩写为(一般这样写) a mod n)得到的是a/n 的余数。

             举个例子：计算表达式 "5 mod 2" 得到 1，因为 5÷2=2...1（5 除以 2 商 2 余1）；而 "9 mod 3" 得到 0，因为 9÷3=3...0；

3.相关性质：

(1)恒等式：

(2)分配律：

(3)除法定义：

    仅当式子右侧有定义时，即 b、n 互质时有：ab mod n = [(a mod n)(b−1 mod n)] mod n，其他情况为未定义的。

(4)乘法逆元：[(ab mod n)(b−1 mod n)] mod n = a mod n.

4.更快的实现：

   对2 的 n 次幂的模，可以通过逐位与运算实现(只适用于正数)。即  x % 2n == x & (2n-1) 也可以写为x % 2n == n&((1